package org.example.Backtracking_algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Empress_N {
    public static ArrayList<List<String>> result = new ArrayList<>();
    public static LinkedList<String> value = new LinkedList<>();

    public static void main(String[] args) {
        //N 皇后

        //按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
        //n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
        //给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
        //每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
        solveNQueens(4);
        prin();
    }

    public static List<List<String>> solveNQueens(int n) {
        boolean[][] used = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(used[i], false);
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) {
            sb.append(".");
        }
        get(n, used, 0,sb);
        return result;
    }

    public static void get(int n, boolean[][] used, int deep,StringBuffer stringBuffer) {
        if (deep == n) {
            result.add(new LinkedList<>(value));
            return;
        }
        StringBuffer sb = new StringBuffer(stringBuffer);
        for (int i = 0; i < n; i++) {
            used[deep][i] = true;
            if (isBattle(used, deep, i, n)) {
                used[deep][i] = false;
                continue;
            }
            sb.setCharAt(i, 'Q');
            value.add(sb.toString());
            get(n, used, deep + 1,stringBuffer);
            value.removeLast();
            sb.setCharAt(i, '.');
            used[deep][i] = false;
        }
    }

    public static boolean isBattle(boolean[][] used, int deep, int index, int n) {
        for (int i = 0; i < deep; i++) {
            if (used[deep - i - 1][index] || (index + i + 1 < n && used[deep - i - 1][index + i + 1]) || (index - i - 1 >= 0 && used[deep - i - 1][index - i - 1]))
                return true;
        }
        return false;
    }

    public static void prin() {
        for (List<String> list : result) {
            System.out.print("[ ");
            for (String integer : list) {
                System.out.println(integer);
            }
            System.out.println(" ]");
        }
        System.out.println();
    }
}
